package com.singzi.leetcode.jianzhiOffer2;

import java.util.*;

public class T0038 {
    public static void main(String[] args) {
        int[] t = new int[]{73,74,75,71,69,72,76,73};
        Solution0038 solution0038 = new Solution0038();
        System.out.println(Arrays.toString(solution0038.LT(t)));
    }
}
class Solution0038 {
    public int[] dailyTemperatures(int[] temperatures) {

        int n = temperatures.length;
        int[]ans = new int[n];
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int index = 0;
        for(int i = 0;i < n;i++){
            if(temperatures[i] == 100) ans[i] = 0;
            else if(map.floorKey(temperatures[i]) != null && map.get(map.floorKey(temperatures[i])) > i){
                for(int j = map.get(map.floorKey(temperatures[i]));j < n;j++){
                    if(temperatures[j] > temperatures[i]) {
                        ans[i] = j - i;
                        map.put(temperatures[i], j);
                        break;
                    }
                }
            }
            else{
                for(int j = i+1;j < n;j++){
                    if(temperatures[j] > temperatures[i]) {
                        ans[i] = j - i;
                        map.put(temperatures[i], j);
                        break;
                    }

                }
            }
        }
        return ans;
    }
    public int[] LT(int[] temperatures){
        int []ans = new int[temperatures.length];
        Deque<Integer> stack = new LinkedList<>();
        for(int i = 0;i < temperatures.length;i++){
            if(stack.isEmpty() || temperatures[i] < temperatures[stack.peek()]){
                stack.push(i);
                continue;
            }
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                int index = stack.pop();
                ans[index] = i-index;
            }
            stack.push(i);
        }
        return ans;
    }
}